//Given the head of a linked list, rotate the list to the right by k places. 
//
// 
// Example 1: 
//
// 
//Input: head = [1,2,3,4,5], k = 2
//Output: [4,5,1,2,3]
// 
//
// Example 2: 
//
// 
//Input: head = [0,1,2], k = 4
//Output: [2,0,1]
// 
//
// 
// Constraints: 
//
// 
// The number of nodes in the list is in the range [0, 500]. 
// -100 <= Node.val <= 100 
// 0 <= k <= 2 * 109 
// 
// Related Topics 链表 双指针 
// 👍 564 👎 0

package leetcode.editor.cn;
 class P61RotateList {
    public static void main(String[] args) {
        Solution solution = new P61RotateList().new Solution();
        ListNode node = new ListNode(1);
        ListNode node1 = new ListNode(2);
        node.next = node1;
        solution.rotateRight(node, 2);
    }
    //leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if (head == null || k == 0) {
            return head;
        }
        ListNode root = head;
        int len = 1;
        while (root.next != null) {
            root = root.next;
            len++;
        }
        if (len == 1) {
            return head;
        }
        k = k % len;
        if (k == 0) {
            return head;
        }
        int mov = len - k;
        ListNode fastNode = head;
        ListNode pre = head;
        while (mov-- > 0) {
            pre = fastNode;
            fastNode = fastNode.next;
        }
        pre.next = null;
        ListNode first = fastNode;
        ListNode listNode = moveToTail(fastNode);
        listNode.next = head;
        return first;

    }

    public ListNode moveToTail(ListNode head) {
        while (head.next != null) {
            head = head.next;
        }
        return head;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}